#include<bits/stdc++.h>
using namespace std;
int T,n,a[200005],c[200005],ymy[200005],vis[1000005],qy[200005],ans;
bool f[200005];
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    cin>>T;
    while(T--)
    {
        memset(c,0,sizeof(c));
        memset(ymy,0,sizeof(ymy));
        memset(vis,0,sizeof(vis));
        memset(qy,0,sizeof(qy));
        ans=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            ymy[i]=vis[a[i]];
            vis[a[i]]=i;
        }
        for(int i=1;i<=n;i++)
        {
            if(ymy[i])
            {
                bool vv=0;
                for(int j=ymy[i]+1;j<i;j++)
                    if(c[j]>=a[i]&&(ymy[j]>ymy[i]||ymy[i]!=j-1))
                    {
                        vv=1;
                        break;
                    }
                    else if(c[j]!=0&&(ymy[j]>ymy[i]||ymy[i]!=j-1)&&qy[j]==1&&ymy[j]!=j-1)
                    {
                        qy[j]=0;
                        ans-=c[j];
                        f[j]=1-f[j];
                    }
                    else if(c[j]!=0&&(ymy[j]>ymy[i]||ymy[i]==j-1)&&qy[j]==0)
                    {
                        qy[j]=1;
                        ans+=c[j];
                    }
                if(vv==1)
                    continue;
                f[i]=f[ymy[i]];
                for(int j=ymy[i]+1;j<i;j++)
                    f[j]=1-f[i];
                c[i]=a[i];
                qy[i]=1;
                ans+=a[i];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
